package com.hanxiaozhang.recursion.violentrecursion;

/**
 * 〈一句话功能简述〉<br>
 * 〈规定1和A对应、2和B对应、3和C对应... 26和Z对应，
 * 那么一个数字字符串比如"111”就可以转化为:"AAA"、"KA"和"AK"，
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果 〉
 *
 * @author hanxinghua
 * @create 2021/10/12
 * @since 1.0.0
 */
public class ConvertToLetterString {

    public static void main(String[] args) {
        System.out.println(number("11111"));
    }


    public static int number(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }


    /**
     * 递归：
     * i之前的位置，如何转化已经做过决定了, 不用再关心，即 str[0... i-1] 已经转换过了
     * i... 有多少种转化的结果
     *
     * @param str
     * @param i
     * @return
     */
    public static int process(char[] str, int i) {
        // i到达终止位置时， 之前转换完的已经够成一个点数 ，最后以为是0？
        if (i == str.length) {
            return 1;
        }
        // 如果str[i]等于'0'，'0'字符没有转换的方式，直接返回0种情况，
        // 因为上游分支，应该去处理这个'0'，我这次处理不，证明这次处理失败，返回0种情况。
        if (str[i] == '0') {
            return 0;
        }
        // 如果str[i]等于'1'
        if (str[i] == '1') {
            // i自己作为单独的部分，后续有多少种方法
            int res = process(str, i + 1);
            if (i + 1 < str.length) {
                // (i和i+1)作为单独的部分，后续有多少种方法
                res += process(str, i + 2);
            }
            return res;
        }
        // 如果str[i]等于'2'
        if (str[i] == '2') {
            // i自己作为单独的部分，后续有多少种方法
            int res = process(str, i + 1);
            // (i和i+1)作为单独的部分并且没有超过26，后续有多少种方法
            if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                // (i和i+1)作为单独的部分，后续有多少种方法
                res += process(str, i + 2);
            }
            return res;
        }
        // str[i] == '3' ~ '9'
        return process(str, i + 1);
    }

    /**
     * 动态规划
     *
     * @param s
     * @return
     */
    public static int dpWays(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        // 字符串长度
        int N = str.length;
        // 暴利结果集数组
        int[] dp = new int[N + 1];
        // 默认是有一种情况
        dp[N] = 1;
        // 从右往左尝试
        for (int i = N - 1; i >= 0; i--) {
            // 等于'0'，不能转换
            if (str[i] == '0') {
                dp[i] = 0;
                // 等于'1'
            } else if (str[i] == '1') {
                // 把上一次的结果给这次
                dp[i] = dp[i + 1];
                // 如果i位置+1小于N，证明 i与i+1可以组成出一种情况
                if (i + 1 < N) {
                    // 这次的结果，即"i+1"的结果 加上 "i+2"的结果
                    dp[i] = dp[i] + dp[i + 2];
                }
                // 等于'2'
            } else if (str[i] == '2') {
                dp[i] = dp[i + 1];
                if (i + 1 < N && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                    dp[i] += dp[i + 2];
                }
                // 等于 '3' ~ '9'
            } else {
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }

}
